package com.alexd.leetcode.solutions.merge_sort.thressWays;
/*
1.聽聽聽聽聽聽閫掑綊瀹炵幇褰掑苟鎺掑簭

鏉ヨ嚜 <https://blog.csdn.net/angelniu1024/article/details/8765618> 

鍩烘湰鎬濇兂锛�
灏嗗緟鎺掑厓绱犲垎鎴愬ぇ灏忓ぇ鑷寸浉鍚岀殑2涓瓙闆嗭紝鍒嗗埆瀵�2涓瓙闆嗗悎杩涜鎺掑簭锛屾渶缁堝皢鎺掑ソ搴忕殑瀛愰泦鍚堝悎骞� 灏变細寰楀埌涓�涓帓濂藉簭鐨勯泦鍚� 鍗充负鎵�姹�
璁惧綊骞舵帓搴忕殑褰撳墠鍖洪棿鏄疪[low..high]锛屽垎娌绘硶鐨勪笁涓楠ゆ槸:
鈶犅犲垎瑙ｏ細灏嗗綋鍓嶅尯闂翠竴鍒嗕负浜岋紝鍗虫眰鍒嗚鐐孤�
鈶÷犳眰瑙ｏ細閫掑綊鍦板涓や釜瀛愬尯闂碦[low..mid]鍜孯[mid+1..high] 杩涜褰掑苟鎺掑簭锛�
鈶⒙犵粍鍚堬細灏嗗凡鎺掑簭鐨勪袱涓瓙鍖洪棿R[low..mid]鍜孯[mid+1..high] 褰掑苟涓轰竴涓湁搴忕殑鍖洪棿R[low..high]銆�
閫掑綊鐨勭粓缁撴潯浠讹細瀛愬尯闂撮暱搴︿负1锛堜竴涓褰曡嚜鐒舵湁搴忥級銆�

*/
public class Solution1 {
	void mergeSort(int[] a,int begin,int end) {
		if(begin == end) {
			return;
		}
		int m = (begin + end)/2;
		mergeSort(a,begin,m);
		mergeSort(a,m+1,end);
		merge(a,begin,end);
	}
	
	void merge(int[] a,int begin,int end) {//m = (begin + end)/2;
		int i,j,k;
		i = begin;
		j = 1 + ((begin + end)>>1); 
		
		while(i <= end && j <= end && i<j) {
			while(i <= end && a[i] < a[j])  
				i++;
			k = j;//鏆傛椂淇濆瓨鎸囬拡j鐨勪綅缃� 
			while(j <= end && a[j] < a[i]) 
				j++;
			if(j > k)
				RotateRight(a , i , j-1 , j-k);   //鏁扮粍a[i...j-1]寰幆鍙崇Щj-k娆�
			i += (j-k+1);  //绗竴涓寚閽堝線鍚庣Щ鍔紝鍥犱负寰幆鍙崇Щ鍚庯紝鏁扮粍a[i....i+j-k]鏄湁搴忕殑 
		}
	}
	
	private void RotateRight(int[] a, int begin, int end, int k) {
		// TODO Auto-generated method stub
		int len = end - begin + 1;
		k %= len;
		Reverse(a , begin , end - k);
		Reverse(a , end - k + 1 , end); 
		Reverse(a , begin , end);  

	}

	private void Reverse(int[] a, int begin, int end) {
		// TODO Auto-generated method stub
		for(; begin < end; begin++ , end--) {
			int temp = a[begin];
			a[begin] = a[end];
			a[end] = temp;
		}

	}

	

	/*//merge涓や釜鏁扮粍锛屾柊鐢宠浜嗕竴娈电┖闂�
	private void merge(int[] a, int[] merge, int begin, int m, int end) {
		// TODO Auto-generated method stub
		//鍙栧乏鍙充袱杈规暟缁勪腑杈冨皬鐨勫厓绱犳斁鍏ユ暟缁刡涓紝鏈�鍚庡緱鍒扮殑鏁扮粍b鍗充负鏈夊簭
		int i = begin;
		int j = m+1;
		int k = begin;
		while(i <= m && j <= end) {
			if(a[i] < a[j]) {
				merge[k++] = a[i++];
			}else {
				merge[k++] = a[i++];
			}
		}
		//
		if(i > m) {
			for(int z = j; z <= end; z++) {
				merge[k++] = a[z];
			}
		}else {
			for(int z = j; z <= m; z++) {
				merge[k++] = a[z];
			}
		}
	}*/
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int in[] = {49,38,65,97,76,13,27};
		new Solution1().mergeSort(in, 0, in.length -1);
		for(int i:in)
			System.out.print(i+" ");
		System.out.println();
	}

}
